home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 288_01 / figure3.tsp < prev    next >
Text File  |  1989-05-23  |  5KB  |  59 lines
  1.                                                       TIME      TOUR   PERCENT
  2.                                              TOUR   IN TICKS  IMPROVED  FROM
  3.                                             LENGTH (.055 SEC)    BY    OPTIMUM
  4.                                             ──────   ──────   ──────   ──────
  5. 33 Cities   Optimum = 10,861        N.N.  |  11994 |     20 |    ─── |   10.4 |
  6.    Karg and Thompson (6)            P─Opt |  10929 |     56 |   1065 |    0.6 |
  7.                                     2─Opt |  11231 |     25 |    763 |    3.4 |
  8.    Input in 107 ticks.              Hybrid|  10861 |     62 |   1133 | OPTIMAL|
  9.                                     3─Opt |  11015 |    755 |    979 |    1.4 |
  10.                                           |        |        |        |        |
  11.                                     Rev.  |  11994 |     20 |    ─── |   10.4 |
  12.                                     P─Opt |  10929 |     61 |   1065 |    0.6 |
  13.                                     2─Opt |  11271 |     20 |    723 |    3.8 |
  14.                                     Hybrid|  10929 |     63 |   1065 |    0.6 |
  15.                                     3─Opt |  11158 |    935 |    836 |    2.7 |
  16.                                           |        |        |        |        |
  17.                                     F.N.  |  62166 |     19 |    ─── |  472.4 |
  18.                                     P─Opt |  13466 |     82 |  48700 |   24.0 |
  19.                                     2─Opt |  11182 |     35 |  50984 |    3.0 |
  20.                                     Hybrid|  11142 |     81 |  51024 |    2.6 |
  21.                                     3─Opt |  10894 |   1514 |  51272 |    0.3 |
  22.                                           |        |        |        |        |
  23. 42 Cities   Optimum = 699           N.N.  |    956 |     31 |    ─── |   36.7 |
  24.    Dantzig, Fulkerson, and Johnson  P─Opt |    780 |    116 |    176 |   11.6 |
  25.    Found in Karg and Thompson (6)   2─Opt |    737 |     44 |    219 |    5.4 |
  26.                                     Hybrid|    709 |    105 |    247 |    1.4 |
  27.    Input in 153 ticks.              3─Opt |    712 |   2440 |    244 |    1.9 |
  28.                                           |        |        |        |        |
  29.                                     Rev.  |    956 |     31 |    ─── |   36.7 |
  30.                                     P─Opt |    742 |    113 |    214 |    6.2 |
  31.                                     2─Opt |    738 |     49 |    218 |    5.6 |
  32.                                     Hybrid|    731 |    149 |    225 |    4.6 |
  33.                                     3─Opt |    719 |   2409 |    237 |    2.9 |
  34.                                           |        |        |        |        |
  35.                                     F.N.  |   4193 |     31 |    ─── |  499.9 |
  36.                                     P─Opt |    772 |    149 |   3421 |   10.4 |
  37.                                     2─Opt |    724 |     74 |   3469 |    3.6 |
  38.                                     Hybrid|    704 |    134 |   3489 |    0.7 |
  39.                                     3─Opt |    752 |   3204 |   3441 |    7.6 |
  40.                                           |        |        |        |        |
  41. 48 Cities   Best known = 11,461     N.N.  |  14241 |     41 |    ─── |   24.3 |
  42.    Held and Karp (5)                P─Opt |  11987 |     74 |   2254 |    4.6 |
  43.                                     2─Opt |  11872 |     58 |   2369 |    3.4 |
  44.    Input in 221 ticks.              Hybrid|  11569 |    141 |   2672 |    0.9 |
  45.                                     3─Opt |  11624 |   2374 |   2617 |    1.4 |
  46.                                           |        |        |        |        |
  47.                                     Rev.  |  14241 |     41 |    ─── |   24.3 |
  48.                                     P─Opt |  11971 |    105 |   2270 |    4.4 |
  49.                                     2─Opt |  11895 |     61 |   2346 |    3.8 |
  50.                                     Hybrid|  11808 |    145 |   2433 |    3.0 |
  51.                                     3─Opt |  11670 |   2461 |   2571 |    1.8 |
  52.                                           |        |        |        |        |
  53.                                     F.N.  |  65714 |     41 |    ─── |  473.4 |
  54.                                     P─Opt |  14940 |    231 |  50774 |   30.4 |
  55.                                     2─Opt |  12402 |     76 |  53312 |    8.2 |
  56.                                     Hybrid|  11717 |    249 |  53997 |    2.2 |
  57.                                     3─Opt |  11619 |   3660 |  54095 |    1.4 |
  58.                    Figure 3. ─ 33, 42, and 48 City Results.
  59.